package com.leetcode.algorithm.y22.m09.w4;

import java.util.ArrayDeque;
import java.util.Deque;

import com.leetcode.algorithm.common.ListNode;

/**
 * 2130. 链表最大孪生和
 * 
 * https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/
 * 
 * @author jie.deng
 *
 */
class Question2130Solution01 {

	public int pairSum(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;
		Deque<Integer> deque = new ArrayDeque<>();
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			deque.offerLast(slow.val);
			slow = slow.next;
		}
		int max = 0;
		while (slow != null) {
			int num = deque.pollLast().intValue();
			if (slow.val + num > max) {
				max = slow.val + num;
			}
			slow = slow.next;
		}

		return max;
	}

}